home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 5 / QRZ Ham Radio Callsign Database - Volume 5.iso / files / tcpip / misc / newlink.txt < prev    next >
Encoding:
Text File  |  1994-11-27  |  8.4 KB  |  365 lines
  1. This is an ASCII representation of the Postscript file in
  2. /hamradio/tcpip/misc/newlink.ps which contains copies of
  3. the presentation slides for non-Postscript equipped users.
  4. ---
  5. Slide #1
  6.  
  7. Toward New Link-Layer
  8. Protocols for
  9. Amateur Packet Radio
  10.  
  11.  
  12. Phil Karn, KA9Q
  13. karn@unix.ka9q.ampr.org
  14. ---
  15. Slide #2
  16.  
  17. AX.25
  18.  
  19. * Created in 1982 - over a decade ago
  20.  
  21. * Based on CCITT X.25 LAPB (itself based on HDLC and SDLC)
  22.  
  23. * Defines datagram-style addressing header for use with LAPB
  24.  
  25. * No allowance for the special problems of radio - collisions, noisy
  26.   radio links, congestion, hidden terminals, etc
  27. ---
  28. Slide #3
  29.  
  30. AX.25 - 11 years later
  31.  
  32. * What do we have now that we didn't have in 1982?
  33.  
  34.   *Far* more powerful computers (100-1000x CPU, RAM, disk)
  35.  
  36.   A variety of RF modems (sort of)
  37.  
  38.   A variety of upper layer protocols (TCP/IP, ROSE, NET/ROM, TexNet)
  39.   
  40.   A *lot* of users
  41.   
  42.   A decade of experiance!
  43. ---
  44. Slide #4
  45.  
  46. AX.25 - Lessons Learned
  47.  
  48. * Link protocols designed for wired networks (espeacially by PTT
  49.   monopolies) don't transition very well to radio
  50.  
  51. * Efficient channel access is a serious problem in real networks
  52.  
  53. * Pure ARQ doesn't work very well, espeacially with QRM
  54.   like 70cm military radar
  55.  
  56. * What a link protocol doesn't do is just as important as what it
  57.   does do (e.g., "connections" are superfluous at the link layer)
  58.  
  59. * We actually need a variety of link protocols, each suited to a
  60.   particular channel (wire, HF, VHF/UHF, satellite), and tied together
  61.   into a uniform Internetwork, e.g., with TCPIP. CLOVER is one
  62.   such protocol, specifically designed for HF. We need more.
  63. ---
  64. Slide #5
  65.  
  66. Forward Error Correction (FEC)
  67.  
  68. Send redundant information to allow correction of (some)
  69. errors without retransmission
  70.  
  71. Exploit Shannon's tradeoff between bandwidth and S/N ratio:
  72.  
  73. C = B log2(1+S/N)
  74.  
  75. The *only* practical way to deal with certain types of interference,
  76. e.g., radar
  77. ---
  78. Slide #6
  79.  
  80. Why Use FEC?
  81.  
  82. * ARQ discards "bad" packets, while FEC uses *all* of the received
  83.   energy to produce a (hopefully) error-free packet
  84.  
  85. * As long as ARQ retransmissions are rare, the loss is minimal
  86.   Rule of thumb: no more than 1% packet loss rate
  87.  
  88. * We are far worse than this on most amateur links!
  89.  
  90. * Small packets may help, but adds considerable overhead
  91.  
  92. * The alternative (increasing power and/or antenna gain) is not always
  93.   practical or economical
  94.  
  95. * Brains over brawn!
  96. ---
  97. Slide #7
  98.  
  99. Why Not Use FEC?
  100.  
  101. * Constant overhead, whether needed or not
  102.  
  103. * Compute-intensive to decode
  104. ---
  105. Slide #8
  106.  
  107. FEC - Some Examples
  108.  
  109. * Block Coding
  110.  
  111.    BCH - AMPS (FM cellular phone) control messages
  112.  
  113.    Reed-Solomon (compact disks)
  114.  
  115.    Hamming (Microsat computer memories)
  116.  
  117. * Convolutional (stream)
  118.  
  119.    CDMA digital cellular
  120.  
  121.    Space communications (VSAT, interplanetary, etc)
  122.  
  123.    V.32/V.32bis telephone modems ("trellis coding")
  124. ---
  125. Slide #9
  126.  
  127. Sample Convolutional Coder
  128.  
  129.         +---------------------------+
  130.            1 -->|           XOR             | --> Symbol #1
  131.         +---------------------------+
  132.           ^       ^   ^       ^   ^
  133.           |       |   |       |   |
  134.         +---+---+---+---+---+---+---+
  135.      Data in -->| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
  136.         +---+---+---+---+---+---+---+
  137.           |   |   |   |           |
  138.           v   v   v   v           v
  139.         +---------------------------+
  140.         |           XOR             | --> Symbol #2
  141.         +---------------------------+
  142.  
  143. k=7("constraint length")
  144. r=1/2("rate")
  145.  
  146. NASA standard
  147. planetary code
  148. ---
  149. Slide #10
  150.  
  151. Decoding Convolutional Codes
  152.  
  153. * Parallel (Viterbi)
  154.  
  155.   Constant decode time
  156.   Limited constraint length - complexity O(2^k)
  157.   Well suited for hardware implementation - chips commercially available
  158.   Best for channels limited by thermal or thermal-like noise, e.g.,
  159.   satellite or spread spectrum
  160.  
  161. * Sequential (Fano, Stack)
  162.  
  163.   Variable decoding time, depends on error rate; either faster or slower
  164.   than Vierbi
  165.   Allows very long constraint lengths (k=32 common)
  166.   With k large, nil probability of incorrect decode (timeout more likely)
  167.   Good for software implementation, espeacially when error rate is low
  168. ---
  169. Slide #11
  170.  
  171. Sequential Decoding
  172.                 +-------
  173.                 |
  174.                 | 11
  175.                 |
  176.             +-------+
  177.             |    |
  178.             |    | 00
  179.                 | 00    |
  180.         +-------+    +-------    (etc)
  181.         |    |    +-------
  182.         |    |    |
  183.         |    | 11    | 10
  184.         |    |    |
  185.         |    +-------+
  186.         |        |
  187. 1        |        | 01
  188.         | 01        |
  189. ^        |        +-------
  190. |  Start -->  --+
  191. v        |        +-------    (etc)
  192.         | 10        |
  193. 0        |        | 00
  194.         |        |
  195.         |    +-------+
  196.         |    |    |
  197.         |    | 01    | 11
  198.         |    |    |
  199.         +-------+    +-------
  200.             |    +-------
  201.             | 10    |
  202.             |    | 01
  203.             |    |
  204.             +-------+
  205.                 |
  206.                 | 10
  207.                 |
  208.                 +-------
  209. ---
  210. Slide #12
  211.  
  212. Sequential Decoding, contd
  213.  
  214. * Decoder has a copy of the encoder, compares received symbols
  215.   with versions regenerated locally
  216.  
  217. * By "intelligent" trial and error, the decoder finds the data
  218.   sequence that produces the best match between locally
  219.   regenerated symbols and the actual received sequence
  220.  
  221. * The decoder also produces a "metric", its estimate of
  222.   the quality of the incoming symbol stream. Like an S-meter,
  223.   only more useful
  224.  
  225. * Decoder is very fast when there are few errors because it doesn't
  226.   have to back up very much; slows down considerably when error
  227.   rate is very high
  228. ---
  229. Slide #13
  230.  
  231. A Fano Decoder in C
  232.  
  233. * "Hard decision" Fano Sequential Decoder in C
  234.  
  235. * Choice of several r=1/2, k=32 polynomial (e.g., NASA standard)
  236.  
  237. * On a 33 MHz 486, decodes 56 kilosymbols (28 kilobits) per second
  238.   on average with input symbol error rate < 2%
  239.  
  240. * Proves feasibility of sequential decoding with modern amateur
  241.   resources
  242. ---
  243. Slide #14
  244.  
  245. Frame Synchronization
  246.  
  247. * Need to reliably detect the beginning of a packet in the presense
  248.   of errors as high as 10% to provide margin for FEC
  249.  
  250. * 8-bit HDLC "flag" unsuitable due to short length
  251.  
  252. * Use pseudorandom sequence with good autocorrelation properties,
  253.   e.g., a PN sequence
  254.  
  255. * The longer the PN sequence, the greater the margin between missing
  256.   frame sync and falsely detecting one in noise. 64 looks good, and is
  257.   easy to implement in software on a 32-bit CPU
  258.  
  259. * Reliable sync enables use of negative acknowledgements (NAKs) to
  260.   request additional information to aid decoding
  261. ---
  262. Slide #15
  263.  
  264. Detecting Sync
  265.  
  266.  
  267. received    +--------------------------+
  268. symbols ---->    | 64-stage shift register  |
  269.         +---------------+----------+
  270.                 |
  271.                  +--+--+
  272.         64-bit ----> | XOR |
  273.         sequence     +--+--+
  274.         mask             |
  275.                 +---+---+
  276.                 | count |
  277.                 | 0's   |
  278.                 +---+---+
  279.                     |
  280.                 v
  281.  
  282.             0-Count > T
  283.              or < 64-T    (T ~=13)
  284. ---
  285. Slide #16
  286.  
  287. Hidden Terminals
  288.  
  289. * Proposed solution: Use Multiple Access with Collision Avoidance
  290.   (MACA), ARRL Computer Networking Conference 1990
  291.  
  292. * Synopsis: Use RTS/CTS (Request-to-Send/Clear-to-Send) handshake
  293.   to hold off hidden terminals before actually sending data
  294.  
  295. * Extra overhead of RTS/CTS handshake can be mitigated with
  296.   large data packets, which use of FEC facilitates
  297. ---
  298. Slide #17
  299.  
  300. One Possible Frame Layout
  301.  
  302. +------+--------+----------+-------------------------+-----------+
  303. | sync | header | hdr tail | data (coded or uncoded) | data tail |
  304. +------+--------+----------+-------------------------+-----------+
  305.                             tail replaced
  306. Header contents (always coded):                with CRC
  307.                             in uncoded
  308. Source address (callsign)                data packets
  309. Destination address
  310. Packet type (RTS, CTS, data, ACK, NAK)
  311. Data length
  312. Data format (data only, parity only, both, neither, interleave on/off)
  313. Decoder metric from last packet received
  314.  
  315. Use r=1/2 systematic code in adaptive ARQ/FEC hybrid to allow
  316. transmission of FEC parity symbols only when needed
  317. ---
  318. Slide #18
  319.  
  320. Sample Protocol Sequence
  321.  
  322.   Sender       Receiver
  323.  +------+    +----------+
  324.     |\
  325.     | \ RTS (length)
  326.        \
  327.         \| Holds off
  328.         /| hidden terminals
  329.        /
  330.       / CTS (length)
  331.     |/
  332.     |\
  333.       \ Data
  334.        \
  335.         \| Rx CRC fails,
  336.         /| requests parity
  337.        /
  338.       / NAK
  339.     |/
  340.     |\
  341.       \ Parity
  342.        \
  343.         \| Rx decodes packet,
  344.         /| returns metric
  345.        /
  346.       / ACK (metric)
  347.     |/
  348.     |\
  349.  
  350. ---
  351. Slide #19
  352.  
  353. Conclusion
  354.  
  355. Although forward error correction (FEC) has been around in
  356. the commercial, military and scientific worlds for some time,
  357. only recently have dramatic advances in personal computers
  358. brought these powerful techniques within the means of the
  359. average radio amateur.
  360.  
  361. Now is the time to experiment with FEC with an eye toward a
  362. whole new generation of amateur packet radio link layer protocols.
  363. ---
  364. EOF
  365.